package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Code104 {
	/*
	 * bfs遍历树
	 */
	
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	if(root==null)
    		return result;
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
    	queue.add(root);
    	map.put(root, 1);
    	ArrayList<Integer> list=null;
    	int step=0;
    	while(!queue.isEmpty()){
    		TreeNode head=queue.poll();
    		int dis=map.get(head);
    		if(step<dis){
    			step++;
    			if(list!=null)
    				result.add(list);
    			list=new ArrayList<Integer>();
    		}
    		list.add(head.val);
    		if(head.left!=null){
    			queue.add(head.left);
    			map.put(head.left, dis+1);
    		}
    		if(head.right!=null){
    			queue.add(head.right);
    			map.put(head.right, dis+1);
    		}
    	}
    	result.add(list);
		return result;
    }
    /*
     * code 103,判断一个二叉树是不是中心对称的
     * 递归求解
     */
    
    
    public boolean isSymmetric(TreeNode root) {
    	if(root ==null)
    		return true;
    	return dfs(root.left,root.right);
    }
    
    public boolean dfs(TreeNode x,TreeNode y){
    	//终止条件
    	if(x==null && y==null)
    		return true;
    	else if(x==null && y!=null)
    		return false;
    	else if(x!=null && y==null)
    		return false;
    	//判断x是否与y对称
    	if(x.val!=y.val)
    		return false;
    	//只要左右子树中有一个不对称，整个树就不对称
    	if(!dfs(x.left,y.right) || !dfs(x.right,y.left))
    		return false;
    	
    	return true;
    }
    /*
     * 102 判断两个二叉树是不是相等
     * 同上对称2叉树的求法，递归。
     * 递归真是个好方法，以前因为不怎么理解，
     * 所以总是觉得出发好写的递归，尽量不是使用递归
     */
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
        	return true;
        if((p==null && q!=null) || (p!=null && q==null))
        	return false;
        if(p.val!=q.val)
        	return false;
        if(!isSameTree(p.left,q.left) || !isSameTree(p.right,q.right))
        	return false;
        return true;
    }
    public static void main(String[] args){
    	Code104 code=new Code104();
    	
    }
}
